package datastructure.hash.solution;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class SolutionEasy {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> integers = new HashSet<>();
        for (int num : nums) {
            boolean add = integers.add(num);
            if (!add) {
                return true;
            }
        }
        return false;
    }
    public int romanToInt(String s) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("I",1);map.put("IV",4);map.put("IX",9);
        map.put("V",5);
        map.put("X",10);map.put("XL",40);map.put("XC",90);
        map.put("L",50);
        map.put("C",100);map.put("CD",400);map.put("CM",900);
        map.put("D",500);
        map.put("M",1000);
        String pre = null;
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            String c = String.valueOf(s.charAt(i));
            boolean b = c.equals("I") || c.equals("X") || c.equals("C");
            if (pre != null) {
                Integer i1 = map.get(pre + c);
                if (i1 != null) {
                    result += i1;
                    pre = null;
                } else {
                    result+=map.get(pre);
                    if (b) {
                        pre = c;
                    } else {
                        result+=map.get(c);
                        pre = null;
                    }
                }
            } else {
                if (b) {
                    pre = c;
                } else {
                    result+=map.get(c);
                }
            }
        }
        if (pre != null) {
            result+=map.get(pre);
        }
        return result;
    }

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int result = 1;
        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0;
        while (start < s.length()) {
            char c = s.charAt(start);
            Integer i = map.get(c);
            if (i == null) {
                map.put(c, start);
                start++;
            } else {
                if (map.size() > result) {
                    result = map.size();
                }
                map.clear();
                start = i+1;
            }
        }
        if (map.size() > result) {
            result = map.size();
        }
        return result;
    }

    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int result = 0;
        int count = 0;
        for (int num : nums) {
            count += num;
            Integer i1 = map.get(count - k);
            if (i1 != null) {
                result += i1;
            }
            Integer orDefault = map.getOrDefault(count, 0);
            map.put(count, orDefault + 1);
        }
        return result;
    }

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer i1 = map.get(target - nums[i]);
            if (i1 != null) {
                return new int[]{i1, i};
            }
            map.put(nums[i], i);
        }
        return null;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode result = new ListNode();
        ListNode temp = null;
        while (l1 != null || l2 != null) {
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;
            int sum = a + b + carry;
            if (sum >= 10) {
                carry = 1;
                sum = sum - 10;
            } else {
                carry = 0;
            }
            if (temp == null) {
                temp = new ListNode(sum);
                result = temp;
            } else {
                temp.next = new ListNode(sum);
                temp = temp.next;
            }
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        if (carry == 1) {
            temp.next = new ListNode(1);
        }
        return result;
    }
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
